package com.biancheng.biancheng.biancheng3;

import java.util.Arrays;

public class 整数拆分 {
    /**
     *
     * @param args
     */
    public static void main(String[] args) {
        整数拆分 ss = new 整数拆分();
        int num = ss.integerBreak(3);
        System.out.println(num);
    }

    //动态规划：
    public int integerBreak(int n){
        if  (n<=2) return 1;
        int arr[]=new int[n+1];
        Arrays.fill(arr,-1);
        arr[1]=1;arr[2]=1;

        for(int i=3;i<=n;i++){
            for(int j=1;j<i;j++){
                arr[i]=max3(arr[i],j*(i-j),j*arr[i-j]);
            }
        }
        return arr[n];
    }

    public int max3(int i,int j,int k){
        return Math.max(i,Math.max(j,k));
    }


}
